package com.lwl.Algorithmic_data_structure.归并排序;

import org.junit.Test;

public class mergeSort {
    @Test
    public void test(){
        int[] array = {
                9, 8, 7, 6, 5, 4, 2, 3, 1
        };
        sort(array);
        for (int i : array) {
            System.out.print(i + " ");
        }
    }
    public void sort(int[] nums){
        mergeSort(nums,0,nums.length-1);
    }
    public void mergeSort(int[] nums,int left,int right){
        if(left >= right){
            return ;
        }
        int mid = left + (right-left)/2;
        mergeSort(nums,left,mid);
        mergeSort(nums,mid+1,right);
        merge(nums,left,mid,right);
    }
    private void merge(int[] nums, int left, int mid, int right) {
        int[] help = new int[right-left+1];
        int index = 0;
        int l = left;
        int r = mid+1;
        while (l <= mid && r <= right){
            help[index++] = nums[l] <= nums[r] ? nums[l++] : nums[r++];
        }
        while (l <= mid){
            help[index++] = nums[l++];
        }
        while (r <= right){
            help[index++] = nums[r++];
        }
        index = 0;
        for (int i = left; i <= right; i++) {
            nums[i] = help[index++];
        }
    }


}
